package dongshi.daddy.skiplist;

import com.alibaba.fastjson.JSON;

import java.util.Random;

/**
 * 跳表类
 * 
 * @author dongyunqi
 * @date 2018年12月5日下午2:31:13
 * @description
 */
public class SkipList {
	// 最大层数，通过改变该值修改最大的索引层数，层数越大效率越高（占用空间越大）
	public static final int MAX_LEVEL = 7;
	// 当前层数
	public int levelCount = 1;
	public Random r = new Random();
	// 头节点
//	public SkipListNode head = new SkipListNode();
	public SkipListNode head = new SkipListNode();

	@Override
	public String toString() {
		return JSON.toJSONString(this);
	}

	public void insert(String data, int score) {
		// 生成随机的层数
		int newLevel = randomLevel();
		// 创建新节点
		SkipListNode newNode = new SkipListNode();
		newNode.score = score;
		newNode.data = data;
		newNode.level = newLevel;
		// 定义一个update数组来保存其之前的level个节点
		// 在之后的操作中方便改变各个节点的指向数组forwards的指向
		// 默认都给头节点（当跳表为空首次插入时是这种情况）
		SkipListNode[] updates = new SkipListNode[MAX_LEVEL];
		for (int i = 0; i < newLevel; i++) {
			updates[i] = head;
		}
		// 默认从头结点开始
		SkipListNode p = head;
		// 改变updates数组为真正的指向
		// 从新节点的最高层循环到最后一层
		for (int i = newLevel - 1; i >= 0; i--) {
			// 如果当前节点当前层的forwards元素不为空，并且值小于当前插入的值
			// 则将节点改变为当前节点的forwards当前值指向的节点
			// 直到找到当前层为空，或者是到达插入点之后节点即p.forwards[i].score > score
			while (p.forwards[i] != null && p.forwards[i].score < score) {
				p = p.forwards[i];
			}
			// 记录当前节点
			updates[i] = p;
		}
		// 从第1层到level层修改update和新节点的forwards的指向
		for (int i = 0; i < newLevel; i++) {
			// 这个改变指向的过程就如同新节点是一堵墙挡住了updates节点指向原有节点
			// 当前updates当前forwards位置元素指向的节点改为新节点的forwards当前位置的指向
			newNode.forwards[i] = updates[i].forwards[i];
			// 当前updates当前forwards位置指向新节点
			updates[i].forwards[i] = newNode;
		}
		// 如果当前层数大于目前最大层则改变当前层数
		if (newLevel > levelCount) {
			levelCount = newLevel;
		}
	}

	public void printAll() {
		SkipListNode p = head;
		// 循环打印第一层所有数据
		while (p.forwards[0] != null) {
			System.out.print(p.forwards[0].score + " ");
			p = p.forwards[0];
		}
		System.out.println();
	}

	// 生成随机的层数
	public int randomLevel() {
		int level = 1;
		for (int i = 1; i < MAX_LEVEL; ++i) {
			if (r.nextInt() % 2 == 1) {
				level++;
			}
		}
		return level;
	}

	// 根据分数查找节点
	public void find(int targetScore) {
		SkipListNode p = head;
		// 从头节点开始一层一层往下找，直到找到目标节点的上一个节点
		for (int i = levelCount - 1; i >= 0; i--) {
			// 如果当前所查找节点不空并且比目标元素小则继续向后
			while (p.forwards[i] != null && p.forwards[i].score < targetScore) {
				p = p.forwards[i];
			}
		}
		// p的forwards的位置0元素不为空，并且0位置元素等于目标元素，则找到，否则不存在
		if (p.forwards[0] != null && p.forwards[0].score == targetScore) {
			System.out.println("找到目标元素为：" + p.forwards[0]);
		} else {
			System.out.println("目标分数：" + targetScore + "没有找到");
		}
	}

	// 删除目标分数
	public void delete(int targetScore) {
		// 存储待删除节点前方的levelCount个节点的数组
		SkipListNode[] updates = new SkipListNode[MAX_LEVEL];
		// 从头节点开始寻找，查找前方所有节点
		SkipListNode p = head;
		// 从最高层头节点开始
		for (int i = levelCount - 1; i >= 0; i--) {
			while (p.forwards[i] != null && p.forwards[i].score < targetScore) {
				p = p.forwards[i];
			}
			// 存储待删除节点前方最后一个层数为i的节点
			updates[i] = p;
		}
		// 如果update的forwards的0索引位置不为空，并且为要删除元素，说明目标元素存在
		if (targetExits(p.forwards[0], targetScore)) {
			// 从最高层开始改变指向
			for (int i = levelCount - 1; i >= 0; i--) {
				// 如果当前元素forwards的i位置不为空，并且指向为待删除元素，则改变引用为删除元素该位置引用
				// updates[i].forwards[i]为目标元素
				if (updates[i].forwards[i] != null && updates[i].forwards[i].score == targetScore) {
					// updates[i].forwards[i].forwards[i]为目标元素i层的指向
					updates[i].forwards[i] = updates[i].forwards[i].forwards[i];
				}
			}
		}
	}

	private boolean targetExits(SkipListNode skipListNode, int targetScore) {
		return skipListNode != null && skipListNode.score == targetScore;
	}
}
